package com.lun.swordtowardoffer2.c11;

public class SingleNonDuplicate {

	public int singleNonDuplicate(int[] nums) {
		int left = 0, right = nums.length / 2;

		while(left <= right) {
			int mid = (left + right) / 2;//这里不必担心溢出
			int index = mid * 2;//groupFirstOriginalIndex
			if(index < nums.length - 1//加着条件避免下条件的潜在数组越界问题（也就是一次数出现在数组末位）
					&& nums[index] != nums[index + 1]) {
				
				if(index == 0 // 一次数出现在数组首位
						|| nums[index - 2] == nums[index - 1]) {
					return nums[index];
				}
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}
				
		return nums[nums.length - 1];//一次数出现在数组末位
	}
	
}
